
Before we can continue with proofs of theorems and lemmas discussed in paper, we propose the following lemmas.

\begin{lemma}
Assume we have only one link with some bandwidth available.  The capacity for the link is maximized when the entire available bandwidth is used\footnote{ This is not trivial since with using more bandwidth, the amount of noise would grow as well.}.
\end{lemma}
\begin{proof}
For a given wireless link with signal strength of $p_1$ and Noise level $N_1$, the capacity formula is as follows.

\[C(B)=B\log (1+\frac{p_{1}{d_{11}^{-\alpha}} }{BN_{1} } )\]

We can compute $2^{C(B)}$ as
\[2^{C(B)}=(1+\frac{p_{1}{d_{11}^{-\alpha}}}{N_{1}}\frac{1}{B})^B=(1+\frac{c}{B})^{B}\]
where $c=\frac{p_{1}{d_{11}^{-\alpha}}}{N_{1}}$ is constant relative to $B$. This function is monastically increasing for $B>0$. Since $2^{C(B)}$ is monastical increasing function, we can deduce that $C(B)$ is also monastically increasing which completes our proof.
\end{proof}


\begin{lemma}
\label{theo:DifferentNoise}
Assume we are given a wireless link and a bandwidth of 1 with two different noise levels. Assume the noise level at (0, b) is equal to $N_1$ and the noise level at (b, 1) is equal to $N_2$. If the transmitter of the link has total power of $p_1$, the capacity is maximized if the power used in (0, b) and (b, 1) are $p_{1}{d_{11}^{-\alpha}} +(N_{2} -N_{1})(1-b)$ and $p_{1}{d_{11}^{-\alpha}} +(N_{1} -N_{2} )b$.
\end{lemma}
\begin{proof}
Assume we divide the power between the two regions by ratio of k and 1-k. We can write the capacity formula as follows.
\fontsize{8.5pt}{9pt}
\[C(k)=b\log (1+\frac{kp_{1}{d_{11}^{-\alpha}} }{bN_{1} } )+(1-b)\log (1+\frac{(1-k)p_{1}{d_{11}^{-\alpha}} }{(1-b)N_{1} } )\]
\normalsize
By solving $C'(k)=0$ we get $k=b+\frac{b(N_{2} -N_{1} )(1-b)}{p_{1}{d_{11}^{-\alpha}} } $ which give us the power per hertz of $p_{1}{d_{11}^{-\alpha}} +(N_{2} -N_{1} )(1-b)$ and $p_{1}{d_{11}^{-\alpha}} +(N_{1} -N_{2} )b$.

\end{proof}

\begin{corollary}
    If a link transmit in multiple channels with different noise levels and with maximum throughput, for any two channels the power per hertz level is higher in channel with lower noise.
\end{corollary}


Now we are ready to provide the proofs for lemmas \ref{theo:nonoverlapcapacity} and \ref{theo:overlapcapacity}.

\begin{proof}[\textbf{Proof of Lemma \ref{theo:nonoverlapcapacity}}]
Assume we have divided the spectrum into (0, x) and (x, 1). Obviously in this case capacity is maximized when we use maximum power on both links. We can write the total capacity formula base on lemma 1 and 2 as follows.

\fontsize{8.5pt}{9pt}
\[C=Bx\log (1+\frac{p_{1}{d_{11}^{-\alpha}} }{xBN_{1} } )+B(1-x)\log (1+\frac{p_{2}{d_{22}^{-\alpha}} }{(1-x)BN_{2} } )\]
\normalsize

We can find the maximum Capacity by solving the following equation.

\[ \begin{array}{ll}
\frac{dC(x)}{dx} = & B(\log (1+\frac{p_{1}{d_{11}^{-\alpha}} }{xBN_{1} } )-\log (1+\frac{p_{2}{d_{22}^{-\alpha}} }{(1-x)BN_{2} } )- \\
 &\frac{p_{1}{d_{11}^{-\alpha}} }{xBN_{1} (1+\frac{p_{1}{d_{11}^{-\alpha}} }{xBN_{1} } )} +\frac{p_{2}{d_{22}^{-\alpha}} }{(1-x)BN_{2} (1+\frac{p_{2}{d_{22}^{-\alpha}} }{(1-x)BN_{2} } )} )
\end{array}\]
And the solution is
\[x=\frac{N_{2} p_{1}{d_{11}^{-\alpha}} }{N_{1} p_{2}{d_{22}^{-\alpha}} +N_{2} p_{1}{d_{11}^{-\alpha}} } \]
And the capacity is
\[C=B\log (1+\frac{p_{1}{d_{11}^{-\alpha}} }{BN_{1} } +\frac{p_{2}{d_{22}^{-\alpha}} }{BN_{2} } )\]
\end{proof}



\begin{proof}[\textbf{Proof of Lemma \ref{theo:overlapcapacity}}]
Based on theorem \ref{theo::powertwolinks} the total capacity is maximized when both links use maximum power. Hence, we can just directly get the result by writing the capacity formula as follows.
\fontsize{8.5pt}{9pt}
\[C=B\log (1+\frac{p_{1}{d_{11}^{-\alpha}} }{p_{2}{d_{21}^{-\alpha}} +BN_{1} } )+B\log (1+\frac{p_{2}{d_{22}^{-\alpha}} }{p_{1}{d_{12}^{-\alpha}} +BN_{2} } )\]
\normalsize
\end{proof}



\begin{proof}[\textbf{Proof of Theorem \ref{theo::powertwolinks}}]
We have the following cases of channel divisions between two wireless links. In each of these cases we prove that the capacity is maximized when the maximum power is used.

\textbf{Case 1:} Two links use non overlapping channels

\textbf{Case 2:} Two links use fully overlapping channels.

\textbf{Case 3:} Two links uses partially overlapping channels.

In case 1, it is trivial that both links should use the maximum power. If we prove that in case 2 the maximum power is used, we have also proven the lemma for case 3 since any excessive power can be used to increase the capacity on both the shared and the non shared part of the spectrum. Hence, we prove the lemma for case 2.

Lets assume that in optimum solution sender 1 uses power level $p'_{1}<p'_{1} $ and sender 2 use power level $p'_{2}<p_{2} $. The capacity can be written as a function of $p'_{2} $ as follows.

\[C(p'_{2} )=\log (1+\frac{p'_{1} d_{11}^{-\alpha } }{p'_{2} d_{21}^{-\alpha } +N_{1} } )+\log (1+\frac{p'_{2} d_{22}^{-\alpha } }{p'_{1} d_{12}^{-\alpha } +N_{2} } )\]

if we $p'_{2}$ and $p'_{1}$ by a constant factor, the total capacity would only increase. Hence, we can assume that in the maximum solution, at least one link is using the maximum power. Without loss of generality, we can assume that it is link 1 and hence $p'_{1}=p_{1}$ is constant. We want to find $p'_{2}$ such that $C$ is maximized. We compute the derivative of $C$ in regards to $p'_{2}$ as follows.

\[
\begin{split}
\frac{dC(p'_{2} )}{dp'_{2} } =&\frac{d_{22}^{-\alpha }}{\left(N_{2} +p_{1} d_{12}^{-\alpha } \right)\left(1+\frac{p'_{2} d_{22}^{-\alpha } }{p_{1} d_{12}^{-\alpha } +N_{2} } \right)}\\
-&\frac{d_{11}^{-\alpha } d_{21}^{-\alpha } p_{1} }{\left(N_{1} +p'_{2} d_{21}^{-\alpha } \right)^{2} \left(1+\frac{p_{1} d_{11}^{-\alpha } }{p'_{2} d_{21}^{-\alpha } +N_{1} } \right)}
\end{split}
\]

The derivative $\frac{dC(p'_{2} )}{dp'_{2} }$ has two roots which are computed as follows.

\[
\begin{array}[t]{l}
\frac{dC(p'_{2} )}{dp'_{2} } =0\to \\
\fontsize{5pt}{7pt}
\begin{array}{l} 
p'_{2} =\\
\begin{array}[t]{l} 
-\frac{N_{1} d_{22}^{-\alpha }}{d_{22}^{-\alpha } d_{12}^{-\alpha } }  \\
-\frac{\sqrt{d_{11}^{-\alpha } d_{22}^{-\alpha } d_{12}^{-\alpha } d_{21}^{-\alpha } \left(p_{1} \right)^{2} +N_{2} d_{11}^{-\alpha } d_{22}^{-\alpha } d_{12}^{-\alpha } p_{1} -N_{1} d_{11}^{-\alpha } d_{22}^{-2\alpha } p_{1} } }{d_{22}^{-\alpha } d_{12}^{-\alpha } }
\end{array} \\
p'_{2} =\\
 \begin{array}[t]{l}
 -\frac{N_{1} d_{22}^{-\alpha }}{d_{22}^{-\alpha } d_{12}^{-\alpha } } \\
 +\frac{\sqrt{d_{11}^{-\alpha } d_{22}^{-\alpha } d_{12}^{-\alpha } d_{4}^{-\alpha } \left(p_{1} \right)^{2} +N_{2} d_{11}^{-\alpha } d_{22}^{-\alpha } d_{12}^{-\alpha } p_{1} -N_{1} d_{11}^{-\alpha } d_{22}^{-2\alpha } p_{1} } }{d_{22}^{-\alpha } d_{12}^{-\alpha } }
 \end{array}
\end{array}
\end{array}
\]



Assume the domain of $p'_{2} $ is $0-\infty $. Note that all the variables used in the above are positive values. Hence, the second value computed for $p'_{2} $ is also negative which is out of the domain of $p'_{2} $.  We can say the following about $C(p'_{2} )$.

\begin{enumerate}
\item \textbf{ }$C(p'_{2} )$ is differentiable for all values of $p'_{2} $.

\item  $\mathop{\lim }\limits_{p'_{2} \to +\infty } C(p'_{2} )=+\infty $

\item  $\frac{dC(p'_{2} )}{dp'_{2} } $ has only one value in the domain of $p'_{2} $

\item  $C(p'_{2} =0)=Some\; Positive\; Value$
\end{enumerate}

From the above information's, we can determine the shape of$C(p'_{2} )$. $C(p'_{2} )$ could only have the two following shapes.

\begin{itemize}
\item $C(p'_{2})$ starts from a positive number and decrease until in hits a local minima. Then $C(p'_{2} )$ start increasing again to infinity.
\item  $C(p'_{2})$ is monotonically increasing function with an Inflection point.
\end{itemize}

Now in reality, we have a maximum power for the link 2.We now show that the capacity is maximized when either $p'_{2} =0$ or $p'_{2} =Max$. We have.

\begin{itemize}
\item For case 1, One can easily verify that $C(p'_{2} )$ is maximized when either $p'_{2} =0$ or $p'_{2} =Max$ depends on what is the maximum power of link 2.

\item For case 2, $C(p'_{2} )$ is maximized when $p'_{2} =Max$.
\end{itemize}
\end{proof}














\begin{proof}[\textbf{Proof of Theorem \ref{theo::main}}]

Assume that theorem \ref{theo::main} is not true. In other words the maximum throughput is achieved when the two links use partial overlapping bandwidth.  In such a case, without loss of generality, we can assume that the first link uses part of spectrum exclusively and a part of spectrum is shared by both links.

In such a case (partial overlap), assume that we cut a small part of spectrum from the shared channel and small part of spectrum from the channel used exclusively used by the first link.  We have state the following about those chunks.

\begin{enumerate}[I]

\item If the throughput is truly maximized, we shouldn't be able to redistribute the power used in two cut chunks of the spectrum to get a better throughput in the two chunks.

\item
 \label{enu:first} If we cut small enough parts, the ratio of the two chunks could be anything. Without loss of generality we can assume that the ratio is 1 to b where $0<b<\infty$.
\end{enumerate}

Assume the $\sigma_{1} $ and $\sigma_{2}$ are the power/hertz level used by senders 1 and 2 un the shared part of the spectrum and $c_{1} +\sigma_{1}$ is the power/hertz level of of wireless link 1 in the exclusive part of the spectrum. Without loss of generality we can assume that the bandwidth of the part we cut from shared part of the spectrum is 1. Based on lemmas 2,3 and 4, we can write the sum of the capacity for the two chunks as follows.

\begin{equation}
\begin{split}
C=&\log (1+\frac{\sigma_{1}{d_{11}^{-\alpha}} }{\sigma_{2}{d_{21}^{-\alpha}} +N_{1} } )\\
+&\log (1+\frac{\sigma_{2}{d_{22}^{-\alpha}} }{\sigma_{1}{d_{12}^{-\alpha}} +N_{2} } )\\
+&b\log (1+\frac{(c_{1} +\sigma_{1}){d_{11}^{-\alpha}} }{N_{1} } )
\end{split}
\end{equation}

\begin{enumerate}[A]
\item \label{enu:second} Now if $c_1<=0$, we can assume that the interference of link 2 is part of the noise and redistribute the power of link 1  based on lemma \ref{theo:DifferentNoise}. With this redistribution, we reduce the power level of link 1 in the shared part of the spectrum. Hence, we simultaneously increasing the capacity of both link 1 and link 2. Hence, in the optimal solution $c_1>0$.
\end{enumerate}

In such a case the power used by link 1 is $b(c_{1} +\sigma_{1} )+\sigma_{1} $. Assume that we divide this power with the ratio of $k$ and $1-k$ between the shared part and the exclusive part of the two chunks. We can write the capacity formula as follows.

\[ \begin{array}{ll}
C= & \log (1+\frac{(1-k)(b(c_{1} +\sigma_{1} )+\sigma_{1} ){d_{11}^{-\alpha}}}{\sigma_{2}{d_{21}^{-\alpha}} +N_{1} } )+ \\
   & \log (1+\frac{\sigma_{2}{d_{22}^{-\alpha}} }{{d_{12}^{-\alpha}}(1-k)(b(c_{1} +\sigma_{1} )+\sigma_{1} )+N_{2} }) + \\
   & b\log (1+\frac{k(b(c_{1} +\sigma_{1} )+\sigma_{1} ){d_{11}^{-\alpha}}}{bN_{1} } )
\end{array} \]

Where $0\le k\le 1$. Since \emph{C} is connected and derivable respect to $k$ for $0\le k\le 1$, \emph{C} is maximized when either $k=0,1$ or $\frac{dC}{dk} =0$. Once can easily verify that the only acceptable answer is $\frac{dC}{dk} =0$. Note that in the optimum solution, the power is distributed with ratio of $\sigma_{1} $ and $b(c_{1} +\sigma_{1} )$ and hence $k=\frac{c_{1} +\sigma_{1} }{b(c_{1} +\sigma_{1} )+\sigma_{1} } $.  Since we assumed that this is the optimal solution and hence optimum distribution of power, the result of solving $\frac{dC}{dk} =0$ should be $k=\frac{c_{1} +p_{1} }{b(c_{1} +p_{1} )+p_{1} } $. Furthermore, \ref{enu:first} would imply that $\frac{dC}{dk} =0\to k=\frac{c_{1} +\sigma_{1} }{b(c_{1} +\sigma_{1} )+\sigma_{1} } $ for any value of \emph{b}.  We know show that this is not possible in any circumstances.

We compute $\frac{dC}{dk} $ and replace $k$ with $k=\frac{c_{1} +\sigma_{1} }{b(c_{1} +\sigma_{1} )+\sigma_{1} } $.  The resulting statement should be equivalent to zero independent of value of \emph{b}.  Hence, we set the statement to zero and factor the resulting equation with respect to $b$. We then show that there is no valid value for system parameters in which the resulting polynomial is equivalent to zero. This would complete our proof.

We did the computation using Matlab symbolic computation toolbox. After simplification of the divisors, the resulting statement is a polynomial of degree \emph{5}.  The polynomial should be equivalent to zero. We sum the coefficient of the 5th degree. The sum should be equivalent to zero as stated in the following equations.

\[c_{1} ^{4} d_{12} ^{-2\alpha} +4c_{1} ^{3} d_{12} ^{-2\alpha} +6c_{1} ^{2} d_{12} ^{-2\alpha} +4c_{1} d_{12} ^{-2\alpha} +d_{12} ^{-2\alpha} =0\]

The only way for the above equation to be equivalent to zero is either $d_{12}=0$ or $c_1 = -1$. However, $d_{12}$ is always a positive number and base on \ref{enu:second}, $c_1$ is as well always positive. Hence, the resulting polynomial could not be equivalent to zero. This would complete our proof.
\end{proof}

\begin{proof}[\textbf{Proof of Theorem \ref{theo:power2}}]
    Assume we have $n$ wireless link with power limit of $P_i$ for each of the senders and $N_k$ is the noise level at receiver of link $k$. Without loss of generality we can assume that the available spectrum is $(0,B)$ and let $N_{min}$ be the minimum noise across the links. Assume in the optimal solution, $s_i(f)$ is power signal of sender of link $i$ for $0<f<B$. Assume link $i$ does not use its maximum power in the optimal solution. In other words, $\int_{0}^{B}{s_i(f)df}<P_i$. Let $p_{diff}$ be $P_i-\int_{0}^{B}{s_i(f)df}>0$ and $p_{max}=Max_{(k,f)}(s_k(f))$ for $k=1..n$ and $0<f<B$. For a constant number $\epsilon$, we make the following changes to optimal solution.
    \begin{itemize}    
        \item For all $1 \leq k=\leq n, k \neq i$ and for $f=(0,\epsilon)$,  $s_k(f)=0$.
        \item $s_k(f)=p_{diff}/\epsilon$ for $f=(0,\epsilon)$.
    \end{itemize}        
    Now we compute the change in capacity of each link and we show that total throughput as well as proportional fairness would increase with such a change. Note that total throughput of each link except $i$ is reduced by these changes.
    
\begin{itemize}
       \item For each link $k$, where the $s_k(f)>0$ for $f=(0,\epsilon)$, the decrease in capacity is
\fontsize{8.5pt}{9pt}
\begin{equation}
\begin{split}
        \Delta(c_k)=& \int_{0}^{\epsilon}{log(1+ \frac{s_k(f)}{N(f)}df}\\
                \leq& \int_{0}^{\epsilon}{log(1+\frac{{\epsilon}p_{max}}{{\epsilon}N_k})df}\\
                   <& {\epsilon}log(1+\frac{p_{max}}{N_{min}})
\end{split}
\end{equation}
\normalsize
        Hence, the maximum decrease in sum of capacity for all the links except $i$ is $(n-1){\zeta}$ where $\zeta={\epsilon}log(1+p_{max})$

        \item For link $i$, the increase in capacity is
\begin{equation}
        \Delta(c_i)= \int_{0}^{\epsilon}{log(1+ \frac{s_i(f)}{N(f)}df}
\end{equation}
Since $s_k(f)=0$ for all $1 \leq k=\leq n, k \neq i$ and for $f=(0,\epsilon)$, N(f) is equal to background noise level in the above and hence we can write $\Delta(c_i)$ as follow:
\begin{equation}
\begin{split}
    \Delta(c_i)= & \int_{0}^{\epsilon}{log(1+\frac{{\epsilon}p_{diff}/\epsilon}{{\epsilon}N_k})df}\\
               = & {\epsilon}log(1+\frac{p_{max}}{{\epsilon}N_k})
\end{split}
\end{equation}
Now we have the following arguments for the two different problem objective.
\begin{itemize}
    \item \softpara{Max sum throughput:} We choose $\epsilon$ is chosen such that ${\epsilon}log(1+\frac{p_{max}}{N_{min}} < 
            {\epsilon}log(1+\frac{p_{diff}}{{\epsilon}N_k})$. For real positive values for $p_{max}$, $N_min$, $p_{diff}$ and $N_k$, $\epsilon= \frac{p_{diff}}{N_i((1+\frac{p_{max}}{N_{min}})^{n}-1})$ satisfy the above inequality. In such a case, the maximum sum throughput can be increased using the above alteration. This is in contradiction with the assumption that the original solution was optimal.
    \item \softpara{Max proportional fairness:} Assume $c_{min}$ and $c_{max}$ are the minimum capacity between all the links in the original solution. The fairness measure of the original solution is $F_{old}=\prod_{k=1}^{n}{c_k}$ and the new fairness measure is $F_{new}=\left(\prod_{k \neq i k=1}^{n}{c_k-\Delta(c_k)}\right){c_i+\Delta(c_i)}$.
        Assume $\eta=\frac{F_{new}}{F_{old}}$. If we find an $\epsilon$ such that $\eta>1$, this would mean that the new proportional fairness measure is greater than the original solution and again contradiction with the assumption that the original solution was optimal. We have
\begin{equation}
\begin{split}
        \eta = & \left(\prod_{k \neq i k=1}^{n}{\frac{c_k-\Delta(c_k)}{c_k}}\right){\frac{c_i+\Delta(c_i)}{c_i}}\\
          \leq & \left(\prod_{k \neq i k=1}^{n}{\frac{c_{min}-\zeta}{c_{min}}}\right){\frac{c_{max}+\Delta(c_{i})}{c_{max}}}\\
          \leq & \left(\frac{c_{min}-\zeta}{c_{min}}\right)^{n-1}{\frac{c_{max}+\Delta(c_{i})}{c_{max}}}
\end{split}
\end{equation}
 If we replace values of $\zeta$ and $\Delta(c_{i})$ and simplify, we get:
 \[
    \eta \leq (1-{\epsilon}a_{1})^{n-1}(1+{\epsilon}a_{2}log(1+\frac{a_3}{\epsilon}))
 \]
 We can state the followings.
  


\[
\begin{array}[t]{ll}
    I)  & \lim_{\epsilon \to 0} \eta=1.\\
    II) & \begin{array}[t]{rl} \frac{d_{\eta}}{d_{\epsilon}}=& (1-a_1{\epsilon})^{n}\times\\
    &\Bigg( \frac{1}{\epsilon}-\frac{a_{2}a_3}{(1+a_3)(1-a_2{\epsilon}(log(1+a_3/{\epsilon})))}\\
    &-n(\frac{1-a_2 {\epsilon} log(1+a_3/{\epsilon})}{1-{a_1}{\epsilon}})\Bigg)\\
    =&(1-a_1{\epsilon})^{n}.\xi
    \end{array}
\end{array}
\]




    Once can easily verify that $\lim_{\epsilon \to 0} \xi=+\infty$ and $(1-a_1{\epsilon})^{n}$ is always positive. Hence, $\frac{d_{\eta}}{d_{\epsilon}}$ is positive when $\epsilon \to +0$.
I and II means that when $\epsilon \to +0$, $\eta \to +1$. This means that there exist a $\epsilon > 0$ such that $\eta > 1$. This completes our proof.
\end{itemize}
\end{itemize}
\end{proof}


\begin{figure}[hbtp]
\label{fig:node}
\begin{center}
\vspace*{-2mm} \scalebox{0.2}{\input{figures/node2.pstex_t}}
\vspace*{-2mm}\caption{\footnotesize Simulating wire with links .}
\label{fig:cell}
\end{center}
\vspace*{-4mm}
\end{figure}

\begin{figure}[hbtp]
\label{fig:wire}
\begin{center}
\vspace*{-2mm} \scalebox{0.35}{\input{figures/wire.pstex_t}}
\vspace*{-2mm}\caption{\footnotesize Simulating edges with links.}
\label{fig:cell}
\end{center}
\vspace*{-4mm}
\end{figure}

\begin{figure}[hbtp]
\label{fig:joint}
\begin{center}
\vspace*{-2mm} \scalebox{0.35}{\input{figures/joint.pstex_t}}
\vspace*{-2mm}\caption{\footnotesize Joint for the outlets.}
\label{fig:cell}
\end{center}
\vspace*{-4mm}
\end{figure}



\begin{proof}[\textbf{Proof of Theorem \ref{theo:hardness1}}]
    To prove the theorem, we have to reduce an NP-complete problem to power assignment problem. We choose 3-coloring of a planar graph with maximum degree of 3 as our NP-complete problem. Note that this reduction prove the theorem for all of the objectives. We define the reduction as below.

    Assume we are given a planar graph, we construct a power assignment problem as follows. Note that in the figures, the black circles are the sender of the links and the white circles are the receivers, where each sender is connected to its receiver with an arrow.
    \begin{itemize}
        \item We replace each node in the graph with the construction of wireless links as shown in figure \ref{fig:node}. Note that figure \ref{fig:node} give us three outlets as shown with the three arrows. Note that the outlets (senders) in this case have a distance of at least $2R$ from each other.
        \item We assume that the outlets could extend with a construction shown in figure \ref{fig:node} called wire.
        \item two outlets could connect together with construction of a joint as shown in figure \ref{fig:joint}
    \end{itemize}
     Let given bandwidth $B=3$. Assume, the distance between every link in the system is $R$ except for the links in the center of each node. We set $\alpha=10$\footnote{the theorem is correct for any $\alpha >2$, however the reduction is more understandable for high value of $\alpha$} and assume that the power level are equal for every link in the system except the center links of each node. Assume that the power level of each sender, except the central node senders, is equal to $p$. We choose background noise $N$ such that $N \simeq p.R^{-\alpha}$. Let immediately close links be two links where sender of one of the link is attached to receiver of another one.
     \begin{itemize}
        \item if a link uses bandwidth of $1$ and no other link immediately attached to it uses the same bandwidth, the maximum interference from other links is $I=p.2^{2-\alpha}=p.2^{-8}$. Hence the throughput of the link is $log(1+2^{8}) \simeq 8$.
        \item if a link share a bandwidth with an immediately close link, then the capacity of one the two links should be almost zero.
     \end{itemize}
      We now can choose the distance of sender and receivers of central links and the power level of senders such that, if the link uses bandwidth of $1$ and assuming that the six links in the proximity of central link do not use the same bandwidth, then the capacity of the link $\simeq 8$. One can easily verify that in such a case, if any of the 6 links in close proximity share the same bandwidth, then the interference at the link doubles and the capacity of the link is reduced to $\leq 7$.
      Now, if the original graph is 3 colorable, we can divide the bandwidth to $3$ channel of size $1$ and then assign a chunk to each links such that $1)$ no two immediately close links share a channel and $2)$ the central link of each node do not share bandwidth with any of the six links in close proximity. Conversely, if the bandwidth could be divided into $3$ channels of size $1$ and links could be assigned channels so that we have $1 and 2$, the the original graph is 3-colorable (each node would receive the channel number of its central link).  We can say the followings.
     \begin{itemize}
        \item \softpara{Max Sum Throughput:} If the throughput achieved is equal to $8m$ where $m$ is the number of links in the construction. then the graph is 3 colorable. Otherwise no 3-coloring exists.
        \item \softpara{Max Proportional Fairness:} If the fairness measure is equal to $8^{m}$ where $m$ is the number of links in the construction, then the graph is 3 colorable. Otherwise no 3-coloring exists.
        \item \softpara{Max Min Throughput} If each node throughput is at least $8$, then the graph is 3 colorable. Otherwise no 3-coloring exists.
     \end{itemize}
     Which complete our reduction and hence, our proof.
\end{proof}



